Digitizing analog data is a technique well-known in the art. There are many advantages available with the use of digitized data that are not available with analog data. Such advantages include longer life without degradation of the data, ease of manipulation of the data, ease of transmission of the data, ease of storage of the data, availability of digital computer processing, and etc. thus, it is frequently preferable to convert analog data into digital data.
For example, video data that is digitized is of higher quality and will last longer without degradation than the analog version thereof. Thus, the conversion of analog video such as is found on a video cassette recorder (VCR) tape into digital video such as is found on a video disk will improve the quality and life of the video. Unfortunately, uncompressed digital video requires storage rates greater than 20 megabytes per second. Such a large storage requirement imposes a burden which makes the storage, retrieval, and transmission of uncompressed digitized video infeasible. Therefore, it is highly advantageous to compress video when digitizing.
The efficient compression of continuous motion digital video is a fundamental problem in this emerging field of computing. There are several known compression techniques in the art which exploit a large amount of redundancy that exists within a frame and between two consecutive frames. The basic idea is, after describing in full detail one image, a second and consecutive image is described by adding only the change (delta) from the first image to the second image. After these changes are applied to the first image, the second frame can be fully created. In known techniques, by virtue of a great deal of commonality between two consecutive images, the information needed to describe the change is typically significantly less than the information needed to describe the second image. For the purpose of describing the image and comparing two consecutive images, each image is divided into an array of blocks. The difference in two images is described by means of describing the change (delta) in two corresponding blocks in two consecutive frames. Each of these blocks is at the same position (i.e., having the same x,y coordinates) in the two frames. For a frame of 800 pixels.times.800 pixels, the entire image can be divided into 10,000 blocks each of which is an 8 pixel.times.8 pixel area. Alternatively, it can be divided into 80.times.80 (6,400) blocks each of which is 10 pixels .times.10 pixels in size.
In an image consisting of a few thousand blocks, most of the blocks will not change from the first frame to the next. In one approach in the prior art, the following format is used:
______________________________________ Block No. Change ______________________________________ 0 No 1 Yes:Delta 2 No . . . . . . etc. etc. ______________________________________
In this format, each change is described one block at a time. If there is no change for a block, a flag is present indicating that there is no change for that block. This scheme has the obvious disadvantage in that regardless of whether a change is present or not, a flag is needed. For example, in a 10,000 block image, if only 100 blocks have a change, 9,900 flags will be needed to indicate that there is no change for those blocks. This implies a minimum of 1,200K bytes of storage space per frame.
An obvious improvement to the previous scheme is to eliminate the flags where no change is present. In this scheme, only those blocks where the changes are present are included. The individual block having a change therein is identified by its x,y coordinate. Each x,y coordinate identification will consume approximately 14 bits. For the case where 100 blocks (approximately 1% of a frame) have changed, the overhead for the block identification will be 1,400 bits (approximately 200 bytes). For the case where 5% of the blocks have change, this overhead will jump to 900 bytes (approximately 1K bytes) per frame. These known methods require too much storage per frame. Thus, there is a need for a method of encoding a location of changes in a sequence of video frames which reduces the amount of overhead required.